package main.adt.queue;

import java.util.Arrays;

/**
 * Created by july on 2015/12/22.
 *
 * 队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。我们把允许插入的一端称为队尾，把允许删除
 * 的一端称为对头。队列又称为先进先出(first in first out)的线性表，简称FIFO结构。
 * 常用操作：
 * 1、初始化建立一个空队列
 * 2、返回队列的长度，返回队列中数据元素个数。
 * 3、加入元素(入队):向队列的rear端插入一个数据元素，队列长度+1
 * 4、删除元素(出队)：从队列的front端删除一个数据元素，队列长度-1，该方法通常返回被删除的数据元素
 * 5、访问队列的前端元素：返回队列的front端的数据元素，但不删除。
 * 6、判断是否为空队列，若为空返回true，不为空返回false。
 * 7、清空队列
 *
 * 队列的顺序存储---顺序队列
 * 顺序队列在加入元素时，由于是在队尾直接加入元素，此时不需要移动任何数据，时间复杂度O(1),但是在执行删除
 * 操作时，由于删除是在队头进行，删除一个数据时，队列中的所有数据都需要前移，时间复杂度为O(n),这种结构和
 * 顺序表没什么区别，在此不再赘述，那么可不可以在执行删除操作时不移动数据呢？如果不去限制队列的元素必须存
 * 储在数组的前n个单元这一条件，出队的性能就会大大增加，也就是说队头不一定在下标为0的位置。这种方式虽然
 * 解决了删除元素时不用移动数据的问题，但是会出现另一个问题“假满”，或者称为“假溢出”:假如队列容量为5，现在
 * 已经放入了5个数据，但删除几个元素后，其实还有空间但我们无法再加入数据。为了解决假满问题可以使用循环队列
 *
 */
public class SequenceQueue<E> {

    private static final int DEFAULT_CAPACITY = 8;  //默认初始容量

    private int capacity;                           //容量
    private int rear = 0;                           //指向队尾元素的下一个位置
    private int front = 0;                          //指向队头元素
    private Object[] data;                          //数据

    public SequenceQueue(){
        this(DEFAULT_CAPACITY);
    }

    public SequenceQueue(int capacity){
        if(capacity <= 0){
            throw new IllegalArgumentException("初始集合时capacity参数值不能小于0");
        }
        this.data = new Object[capacity];
        this.capacity = capacity;
    }

    /**
     * 入队
     * 当rear的值等于capacity-1时就表示队列已满
     * @param element
     */
    public void add(E element){
        if(rear > capacity - 1){
            throw new IndexOutOfBoundsException("当前队列已满,无法插入数据");
        }
        data[rear++] = element;
    }

    /**
     * 出队
     * 此操作会出现假满问题，虽然还有剩余空间，但无法加入数据，如果要重复利用被删除的数据空间
     * 可用循环队列实现
     * @return
     */
    @SuppressWarnings("unchecked")
    public E remove(){
        if(isEmpty()){
            throw new IndexOutOfBoundsException("当前队列为空，无法删除数据");
        }
        E oldData = (E) data[front];
        data[front++] = null;
        return oldData;
    }

    /**
     * 访问队头元素
     * @return
     */
    @SuppressWarnings("unchecked")
    public E get(){
        if(isEmpty()){
            throw new NullPointerException("队列为空，无法访问队头元素");
        }
        return (E) data[front];
    }

    /**
     * 判断是否为空队列
     * @return
     */
    public boolean isEmpty(){
        return front == rear;
    }

    /**
     * 返回队列的长度
     * @return
     */
    public int size(){
        return rear - front;
    }

    /**
     * 清空队列
     */
    public void clear(){
        Arrays.fill(data, null);
        front = rear = 0;
    }

    /**
     *  复写toString方法，便于查看集合中的数据
     */
    @Override
    public String toString() {
        if(isEmpty()){
            return "[]";
        }
        StringBuilder sb = new StringBuilder("[");
        Object temp;
        for(int i = front;i < rear;i++){
            temp = data[i];
            if(temp != null){
                sb.append(temp.toString()).append(',');
            }else{
                sb.append("Null").append(',');
            }
        }
        int len = sb.length();
        sb.delete(len-1,len).append("]");
        return sb.toString();
    }

}
